package algorithms.sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.logging.Logger;

/**
 * 归并排序<br>
 *
 * <br>算法思想：<br>
 * 归并的意思就是将两个有序的数组合成一个更大的有序数组，如果采用自顶向下的思想，那就得保证从上往下对大数组进行分割
 * 成小数组，也就形成了递归。例如sort。
 * 非递归的实现（自底向上）例如sort2
 *
 */
public class MergeSort {

    private static Logger logger = Logger.getLogger(MergeSort.class.getPackage().getName());

	private static Comparable[] aux;

	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[j] = a[i];
		a[i] = t;
	}

    /**
     * 递归方式实现
     * @param a 待排序数组
     */
	public static void sort(Comparable[] a){
		aux = new Comparable[a.length];
		sort(a, 0, a.length - 1);
	}

    //递归方式的实现
    private static void sort(Comparable[] a, int lo, int hi){
        if(lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    /**
     * 非递归方式实现
     * @param a 待排序数组
     */
	public static void sort2(Comparable[] a){
		int N = a.length;
		aux = new Comparable[N];
		for(int sz = 1; sz < N; sz = sz + sz)   //外循环控制子数组大小
        {
			for(int lo = 0; lo < N - sz; lo +=sz + sz)  //内循环控制lo, mid hi
            {
				merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1 ));
			}
		}
	}
	
	//合并两个子数组
	public static void merge(Comparable[] a, int lo, int mid, int hi){
		int i = lo, j = mid + 1;
		
//		for(int k = lo; k <= hi; k++)
//			aux[k] = a[k];
        System.arraycopy(a, lo, aux, lo, (hi - lo + 1));

		for(int k = lo; k <= hi; k++){
			if(i > mid) a[k] = aux[j++];
			else if(j > hi)	a[k] = aux[i++];
			else if(less(aux[j], aux[i]))	a[k] = aux[j++];
			else	a[k] = aux[i++];
		}
	}
	
	public static void show(Comparable[] a, int type){
        if(type == 0){
            logger.info("递归方式排序：\n" + Arrays.toString(a));
        }else{
            logger.info("非递归方式排序：\n" + Arrays.toString(a));
        }
	}
	
	public static void main(String[] args) {
        logger.info("归并排序Demo");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            String l = br.readLine();
            String[] array0 = l.split("\\s");
            String[] array1 = array0.clone();
            //recursive
            MergeSort.sort(array0);
            MergeSort.show(array0, 0);
            //non-recursive
            MergeSort.sort2(array1);
            MergeSort.show(array1, 1);

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

	
	
}
